function AVL_Node()
{
	this.left=null;
	this.right=null;
	this.parent=null;
    this.key=null;
	this.value=null;
	this.prop=null;
}
function AVL_Tree() {
    this.root=null;
    this.end=null;
    this.size=0;
    this.prop=null;

}
//n is a AVL_Node
// return the next increasing node
function avl_increase(n)
{

    var nn=new AVL_Node();
    if(n==null)
    {
        return nn;
    }

    var root=n;
    while(root.parent!=null&&root.parent.right==root)
    {
        root=root.parent;
    }
    if(root.parent!=null)
    {
        if(root.parent.right==null)
        {
            root=root.parent;
            root.right=nn;
            nn.parent=root;
        }
        else
        {
            root=root.parent.right;
            while(root.left!=null)
            {
                root=root.left;
            } 
            root.left=nn;
            nn.parent=root;
        }
    }
    else
    {

        while(root.left!=null)
        {
            root=root.left;
        }
        root.left=nn;
        nn.parent=root;
    }
    return nn;
}
//n is a AVL_Node
//return previous AVL_Node
function avl_decrease(n)
{
    if(n==null||n.parent==null)
    {
        return null;
    }

    var root=n;
    while(root.parent!=null&&root.parent.left==root)
    {
        root=root.parent;
    }
    if(root.parent!=null)
    {
        root=root.parent.left;
        while(root.right!=null)
        {
                root=root.right;
        } 
        return root;
        
    }
    else
    {

        while(root.right!=null)
        {
            root=root.right;
        }
        return root;
    } 
}
//if the tree has the key,return the node
//else return the node that will be increase
function my_find(tree,key)
{ 
    if(tree==null)
    {
        return null;
    }
    var n=tree.root;
    if(n==null)
    {
        return null;
    }
    while(n.key!=key)
    {
        if(n.left==null&&key<n.key)
        {
            return n;
        } 
        if(n.right==null&&key>n.key)
        {
            return n;
        }
        if(n.left==null&&n.right==null)
        {
            return n;
        }
        if(key>n.key)
        {
            n=n.right;
        }
        else
        {
            n=n.left;
        }
    }
    return n;
}
function avl_find(tree,key)
{
    var n=my_find(tree,key);
    if(n.key==key)
    {
        return n;
    }
    else
    {
        return null;
    }
}



function Node(value){
    this.value=value;
    this.Prev=null;
    this.Next=null;
    this.traits=null;
}
function node_overlying(n,v)
{
    var n1=new Node(v);
    n1.Next=n;
    if(n!=null)
    {
        n.Prev=n1;
    }
    return n1; 
}

//n1 >= n2  it's not based on value??????
function compare_two_node(n1,n2) {
    if(n1==null||n2==null)
    {
        return false;
    }
    var temp=n1;
    var node1=null,node2=null;
    var i=0
    while(temp!=null)
    {
        node1=node_overlying(node1,temp);
        temp=temp.parent;
        i++;
    }
    temp=n2;
    var j=0;
    while(temp!=null)
    {
        node2=node_overlying(node2,temp);
        temp=temp.parent;
        j++;
    } 
    var nit=null,nit1=null;
    if(j>i)
    {
        nit=node2;nit1=node1;
        while(nit!=null)
        {
            if(nit1==null||nit.value!=nit1.value)
            {
                if(nit.value.parent.left==nit.value)
                {
                    return true;
                }
                else
                {
                    return false;
                }
            }
            nit=nit.Next;
            nit1=nit1.Next;
        }
    }
    else
    {
        nit=node1;nit1=node2;
        while(nit!=null)
        {
            if(nit1==null||nit.value!=nit1.value)
            {
                if(nit.value.parent.left==nit.value)
                {
                    return false;
                }
                else
                {
                    return true;
                }
            }
            nit=nit.Next;
            nit1=nit1.Next;
        }
    }
    
    return false;
}
//the node that > n
function successor(n)
{
    if(n==null)
    {
        return null;
    }
    var x=n;
    var node=null;
    if(x.right!=null)
    {
        node=x.right;
        while(node.left!=null)
        {
            node=node.left;
        }
        return node;
    }
    else
    {
        node=x.parent;
        while(node!=null&&(x==node.right))
        {
            x=node;
            node=node.parent;
        }
        return node;
    }
    return node;

}
//the next node that <n
function predecessor(n) {

    var node=null;
    if(n==null)
    {
        return null;
    } 
    var x=n;
    if(x.left!=null)
    {
        node=x.left;
        while(node.right!=null)
        {
            node=node.right;
        }
        return node;
    } 
    else
    {
        node=x.parent;
        while((node!=null)&&(x==node.left))
        {
            x=node;
            node=node.parent
        }
        return node;
    }
    return node;
}

function avl_insert(tree,key,value)
{
    var n=my_find(tree,key);
    if(n==null)
    {
        var nn=avl_increase(tree.end);
        nn.key=key;nn.value=value;
        tree.size++;
        tree.end=nn;
        tree.root=nn;
        return;
    }
    if(key==n.key)
    {
        n.key=key;
        n.value=value;
    }  
    else
    {
        var nn=avl_increase(tree.end);
        tree.size++;
        tree.end=nn;
        if(nn.parent==n&&((n.left==nn&&key<n.key)||(n.right==nn&&key>n.key)))
        {
            nn.key=key;
            nn.value=value;
        }
        else
        {
            var temp=nn;
            var temp1=null,data=null;

            if(compare_two_node(nn,n))
            {
               
                while(temp!=n)
                {
                    temp1=predecessor(temp);
                    data=temp.key;temp.key=temp1.key;temp1.key=data;
                    data=temp.value;temp.value=data;temp1.value=data;
                    data=temp.prop;temp.prop=temp1.prop;temp1.prop=data;
                    temp=temp1;
                }
            }
            else
            {
                while(temp!=n)
                {
                    temp1=successor(temp);
                    data=temp.key;temp.key=temp1.key;temp1.key=data;
                    data=temp.value;temp.value=data;temp1.value=data;
                    data=temp.prop;temp.prop=temp1.prop;temp1.prop=data;
                    temp=temp1;
                } 
            }
            n.key=key;n.value=value;
        } 
    }
}
//n is a AVL_Node 

function avl_delete_node(tree,n)
{
	if(n==null||tree==null||tree.end==null)
	{return ;}
    var nn=avl_decrease(tree.end),nn1=tree.end;
    tree.end=nn;

    if(nn1!=n)
    {
        var temp=n,temp1=null,data=null;
       // console.log("he:",n.key);
        if(compare_two_node(nn1,n)>0)
        {
           // console.log("he1"); 
            while(temp!=nn1)
            {
                temp1=successor(temp);
                data=temp.key;temp.key=temp1.key;temp1.key=data;
                data=temp.value;temp.value=data;temp1.value=data;
                data=temp.prop;temp.prop=temp1.prop;temp1.prop=data; 

                temp=temp1;

            }
        }
        else
        {
           // console.log("he1"); 
            while(temp!=nn1)
            {
                temp1=predecessor(temp);
                data=temp.key;temp.key=temp1.key;temp1.key=data;
                data=temp.value;temp.value=data;temp1.value=data;
                data=temp.prop;temp.prop=temp1.prop;temp1.prop=data; 
                temp=temp1;

            }

        }
    }
    var r=nn1.parent;
    if(r==null)
    {
        tree.root=null;
    }
    else
    {
        if(r.left==nn1)
        {
            r.left=null;
        }    
        else{
            r.right=null;
        }
        nn1.parent=null;
    }
}

function avl_delete_key(tree,key)
{
    var n=my_find(tree,key);
    if(n.key==key)
    {
        //console.log(n.key);
        avl_delete_node(tree,n);
    }


}
var at=new AVL_Tree();
avl_insert(at,4,"4");
avl_insert(at,5,"5");

//console.log(at.root.key);
//console.log(at.root.left.key);
avl_insert(at,1,"1");
avl_insert(at,9,"9");
avl_insert(at,19,"19");
avl_delete_key(at,1);

//avl_delete_node(at,avl_decrease(at.end));

console.log(at.root.key);
console.log(at.root.left.key);
console.log(at.root.right.key);
console.log(at.root.left.left.key);
//console.log(at.root.left.right.key);
console.log(avl_decrease(at.end).key)
var n=my_find(at,4);






// function rb_right_rotate(tree,y)
// {
//     var x=y.left;
//     y.left=x.right;
//     if(x.right!=null)
//     {
//         x.right.parent=y;
//     }
//     x.parent=y.parent;
//     if(y.parent==null)
//     {
//         tree.root=x;
//     }
//     else
//     {
//         if(y==y.parent.right)
//         {
//             y.parent.right=x;
//         }
//         else
//         {
//             y.parent.left=x;
//         }
//     }
//     x.right=y;
//     y.parent=x;
// }
// function rb_left_rotate(tree,x)
// {
//     var y=x.right;
//     x.right=y.left;
//     if(y.left!=null)
//     {
//         y.left.parent=x;
//     }
//     y.parent=x.parent;
//     if(x.parent==null)
//     {
//         tree.root=y;
//     }  
//     else
//     {
//         if(x.parent.left==x)
//         {
//             x.parent.left=y;
//         }
//         else
//         {
//             x.parent.right=y;
//         }
//     }
//     y.left=x;
//     x.parent=y;
// }
